using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace GeoAzure.Core
{
    internal class Searcher<T>
        where T : class
    {
        public IEnumerable<T> Query(IndexEntry<T> rootEntry, GeoRectangle queryRectangle)
        {
            var results = new List<T>();
            var nodesToQuery = new Stack<IndexWalk<T>>(20);
            nodesToQuery.Push(new IndexWalk<T>(rootEntry));
            Query(queryRectangle, nodesToQuery, results, null);

            return results;
        }

        public IEnumerable<T> QueryWithinDistance(IndexEntry<T> rootEntry, Location centerLocation, double distance)
        {
            if (distance < 0d || distance > Math.PI * Constants.EarthRadius)
                throw new ArgumentOutOfRangeException("distance", distance, "The specified distance is out of range. Must be positive and less than half earth great circonference.");
            GeoRectangle boundingRectangle1;
            GeoRectangle boundingRectangle2;
            bool hasTwoBoundingRects = CalculateBoundingRectangleForDistanceQuery(centerLocation, distance, out boundingRectangle1, out boundingRectangle2);

            var results = new List<T>();
            var nodesToQuery = new Stack<IndexWalk<T>>(20);

            nodesToQuery.Push(new IndexWalk<T>(rootEntry));

            Predicate<IndexEntry<T>> distanceFilter =
                entry => entry.Bounds.Center.DistanceTo(centerLocation) <= distance;

            Query(boundingRectangle1, nodesToQuery, results, distanceFilter);
            if (hasTwoBoundingRects)
            {
                nodesToQuery.Push(new IndexWalk<T>(rootEntry));
                Query(boundingRectangle2, nodesToQuery, results, distanceFilter);
            }

            return results;
        }

        private static bool CalculateBoundingRectangleForDistanceQuery(Location centerLocation, double distance, out GeoRectangle boundingRect1, out GeoRectangle boundingRect2)
        {
            // see http://janmatuschek.de/LatitudeLongitudeBoundingCoordinates for an explanation of what is going on here
            var angularRadius = distance / Constants.EarthRadius;
            var topLat = centerLocation.Latitude + angularRadius;
            var bottomLat = centerLocation.Latitude - angularRadius;
            if (topLat > Location.MaxLatitude)  // we passed the North pole, so we take a rectangle around it
            {
                boundingRect1 = GeoRectangle.Create(new Location(Location.MaxLatitude, Location.MinLongitude),
                                                    new Location(bottomLat, Location.MaxLongitude));
                boundingRect2 = GeoRectangle.NullRectangle;
                return false;
            }
            if (bottomLat < Location.MinLatitude)   // deal with South pole
            {
                boundingRect1 = GeoRectangle.Create(new Location(topLat, Location.MinLongitude),
                                                    new Location(Location.MinLatitude, Location.MaxLongitude));
                boundingRect2 = GeoRectangle.NullRectangle;
                return false;
            }
            var deltaLong = Math.Asin(Math.Sin(angularRadius) / Math.Cos(centerLocation.Latitude));
            var leftLong = centerLocation.Longitude - deltaLong;
            var rightLong = centerLocation.Longitude + deltaLong;

            // deal with the 180th meridian
            if (leftLong < Location.MinLongitude)
            {
                // (latmin, lonmin + 2 PI), (latmax, PI) and (latmin, -PI), (latmax, lonmax)
                boundingRect1 = GeoRectangle.Create(new Location(topLat, leftLong + 2 * Math.PI),
                                                    new Location(bottomLat, Location.MaxLongitude));
                boundingRect2 = GeoRectangle.Create(new Location(topLat, Location.MinLongitude),
                                                    new Location(bottomLat, rightLong));
                return true;
            }

            if (rightLong > Location.MaxLongitude)
            {
                //  (latmin, lonmin), (latmax, PI) and (latmin, -PI), (latmax, lonmax - 2PI).
                boundingRect1 = GeoRectangle.Create(new Location(topLat, leftLong),
                                                    new Location(bottomLat, Location.MaxLongitude));
                boundingRect2 = GeoRectangle.Create(new Location(topLat, Location.MinLongitude),
                                                    new Location(bottomLat, rightLong - 2 * Math.PI));
                return true;
            }
            // normal case
            boundingRect1 = GeoRectangle.Create(new Location(topLat, leftLong), new Location(bottomLat, rightLong));
            boundingRect2 = GeoRectangle.NullRectangle;
            return false;
        }

        private static void Query(GeoRectangle queryRectangle, Stack<IndexWalk<T>> nodesToQuery, ICollection<T> results, Predicate<IndexEntry<T>> entryFilter)
        {
            while (nodesToQuery.Count > 0)
            {
                IndexWalk<T> indexWalk = nodesToQuery.Pop();
                var expectedlsn = indexWalk.ExpectedLsn;
                var treeNode = indexWalk.Node;
                treeNode.LockForReading();
                long currentLsn = treeNode.Lsn;
                TreeNode<T> rightSibling = treeNode.RightSibling;
                // if we detect a split (change in LSN), then move along the rightlink chain
                while (currentLsn != expectedlsn)
                {
                    Debug.Assert(rightSibling != null, "The searched node has no right sibling, but its LSN is obsolete, indicating that a split was performed.");
                    rightSibling.LockForReading();
                    currentLsn = rightSibling.Lsn;
                    nodesToQuery.Push(new IndexWalk<T>(rightSibling));
                    rightSibling.ReleaseReadLock();
                    // move along the right link chain
                    rightSibling = rightSibling.RightSibling;
                }

                foreach (IndexEntry<T> entry in treeNode.Entries)
                {
                    if (treeNode.IsLeaf) // for leaf nodes, check if an element is contained within the query rectangle
                    {
                        // note that we do not need to take any kind of read lock here
                        // indeed a leaf node entry is immutable (bounds cannot change)
                        if (queryRectangle.Contains(entry.Bounds))
                            if (entryFilter != null)
                            {
                                if (entryFilter(entry))
                                    results.Add(entry.Element);
                            }
                            else
                            {
                                results.Add(entry.Element);
                            }
                    }
                    else
                    {
                        // for child index nodes, recurse if the query rectangle has an intersection 
                        // with the node bounding rectangle
                        var childNode = entry.Node;
                        Debug.Assert(childNode != null);
                        if (queryRectangle.Intersects(entry.Bounds))
                            nodesToQuery.Push(new IndexWalk<T>(entry));
                    }
                }
                treeNode.ReleaseReadLock();
            }
        }
    }
}